// // class Node{
// //   constructor(data){
// //     this.parent = parent;
// //     this.data = data;
// //     this.children = [];
// //   }
// // }
// // class Node{
// //   constructor(){
// //     this.firstChild = null;
// //     this.sibling = null;
// //   }
// // }

class Node{
    constructor(data){
      this.parent = null;
      this.data = data;
      this.left = null;
      this.right = null;
    }
}
//   class Tree{
//     constructor(){
//        this.root = null;
//        this._size = 0;
//     }
//     insert(data) {
//         let dir = this._insertLeft = !this._insertLeft;// 插入方向
//         function insertIt(node, data) {
//           if (node.data === data) {
//             return false;
//           } else if (!node.left) {
//             node.left = new Node(data);
//             node.left.parent = node;
//             return true;
//           } else if (!node.right) {
//             node.right = new Node(data);
//             node.right.parent = node;
//             return true;
//           } else {
//             if (dir === true) {
//               return insertIt(node.left, data);// 递归
//             } else {
//               return insertIt(node.right, data);// 递归
//             }
//           }
//         }
//         let ret = false;
//         if (!this.root) {
//           this.root = new Node(data);
//           ret = true;
//         } else {
//           ret = insertIt(this.root, data);
//         }
//         if (ret) {
//           this._size++;
//         }
//         return ret;
//     }
//     find(data) {
//         let ret = null;
//         function findIt(node, data) {
//           if (node) {
//             if (node.data === data) {
//               ret = node;
//             } else {
//               findIt(node.left, data); // 递归
//               findIt(node.right, data); // 递归
//             }
//           }
//         }
//         findIt(this.root, data);
//         return ret;
//     }
//     transplant(node, child) {
//         if (node.parent == null) {
//           this.root = child;
//         } else if (node == node.parent.left) {
//           node.parent.left = child;
//         } else {
//           node.parent.right = child;
//         }
//         if (child) {
//           child.parent = node.parent;
//         }
//     }
    // remove(data) {
    //     let p = this.find(data);
    //     if (p) {
    //       this.removeNode(p);// 方便递归
    //       this._size--;
    //     }
    // }
//     removeNode(node) {
//         // replace表示删除之后顶替上来的结点
//         // parent为replace结点的父结点
//         // 如果删除的结点左右“孩子”都有
//         if (node.left != null && node.right != null) {
//           let succ = null;
//           for (succ = node.right; succ.left != null; succ = succ.left); // 找到后继
//           node.data = succ.data; // 覆盖值
//           this.removeNode(succ); // 递归删除，只可能递归一次
//         } else {
//           // “叶子”或只有一个“孩子”的情况
//           let child = node.left || node.right || null;
//           this.transplant(node, child);
//         }
      
//     }
//     size(){
//         return this._size; // this.getNodeSize(this.root)
//     }
//     getNodeSize(node){
//         if (node == null){
//           return 0;
//         }
//         let leftChildSize = this.getNodeSize(node.left);
//         let rightChildSize = this.getNodeSize(node.right);
//         return leftChildSize + rightChildSize + 1;
//     }
//     height(){
//         return this.getNodeHeight(this.root);
//     }
//       // 获取指定结点的度
//     getNodeHeight(node){
//         if (node === null){// 递归出口
//           return 0;
//         }
//         let leftChildHeight = this.getNodeHeight(node.left);
//         let rightChildHeight = this.getNodeHeight(node.right);
//         let max = Math.max(leftChildHeight, rightChildHeight);
//         return max + 1; // 加上自己本身
//     }
//     // inOrder(callback) {// 左中右
//     //     this._forEach(this.root, callback, "middle");
//     // }
//     //   preOrder(callback) {// 中左右
//     //     this._forEach(this.root, callback, "pre");
//     //   }
//     //   postOrder(callback) {
//     //     this._forEach(this.root, callback, "post");
//     //   }
//     // _forEach(node, callback, type) {
//     //     if (node) {
//     //       if (type === "middle") {// 中序遍历
//     //         this._forEach(node.left, callback, type);
//     //         callback(node);
//     //         this._forEach(node.right, callback, type);
//     //       } else if (type === "pre") {// 前序遍历
//     //         callback(node);
//     //         this._forEach(node.left, callback, type);
//     //         this._forEach(node.right, callback, type);
//     //       } else if (type === "post") {// 后序遍历
//     //         this._forEach(node.left, callback, type);
//     //         this._forEach(node.right, callback, type);
//     //         callback(node);
//     //       }
//     //     }
//     // }
//     // 5.2.8　深度优先遍历的非递归实现
//     // preOrder(callback){
//     //     let node = this.root;
//     //     let stack = [];
//     //     node && stack.push(node); // 先处根的先放进去
//     //     while(stack.length){
//     //       let node = stack.pop();// 不能全部压入再弹出，应立即弹出
//     //       callback(node); 
//     //       // 栈会先进后出，因此先压入right再压入left
//     //       let {left, right} = node;
//     //       if(right){
//     //         stack.push(right);
//     //       }
//     //       // 当left被弹出来执行后，它又会放进它左边的右子树
//     //       // 因此会延后其兄弟right的处理
//     //       if(left){
//     //         stack.push(left);
//     //       }
//     //     }
//     // }
//     // inOrder(callback){
//     //     let node = this.root;
//     //     let stack = [], hasRight = false;
//     //     node && stack.push(node); // 根结点入栈
//     //     while (stack.length) {
//     //       // 继续将左边的放进
//     //       while (node.left) {
//     //         stack.push(node.left);
//     //         node = node.left;
//     //       }
//     //       hasRight = false;
//     //       // 如果没有左孩子结点
//     //       while (stack.length && !hasRight) {
//     //         node = stack.pop();// 弹出处理它
//     //         let right = node.right;
//     //         callback(node);
//     //         if (right) {// 如果有右孩子结点，放进去，然后回到第一个循环，找它的左孩子结点
//     //           stack.push(right);
//     //           node = right;
//     //           hasRight = true;
//     //         }
//     //       }
//     //     }
//     // }
//     // // postOrder(callback){
//     // //   let node = this.root;
//     // //   let stack = [], visited = false;
//     // //   node && stack.push(node);
//     // //   while (stack.length) {
//     // //     node = stack[stack.length - 1];// 没有直接弹出来，而是使用了stack.peek方法
//     // //     if ((!node.left && !node.right) || (visited &&
//     // //       (visited == node.left || visited == node.right))) {
//     // //       callback(node);
//     // //       stack.pop();
//     // //       visited = node;
//     // //     } else {
//     // //       if (node.right) {
//     // //         stack.push(node.right);
//     // //       }
//     // //       if (node.left) {
//     // //         stack.push(node.left);
//     // //       }
//     // //     }
//     // //   }
//     // // }
//     // postOrder(callback){// 与前序遍历长得很像的postOrder
//     //   let node = this.root;
//     //   let stack = [];
//     //   let out = [];
//     //   node && stack.push(node); // 根结点入栈
//     //   while(stack.length){
//     //     let node = stack.pop();// 不能全部压入再弹出，应立即弹出
//     //     out.push(node); // 先放进去
//     //     // 栈会先进后出，因此先压入right再压入left
//     //     let {left, right} = node;
//     //     if(right){
//     //       stack.push(right);
//     //     }
//     //     if(left){
//     //       stack.push(left);
//     //     }
//     //   }
//     //   while(out.length){
//     //     callback(out.pop());
//     //   }
//     // }

//     // 5.2.9　优化深度优先遍历的非递归实现
    // preOrder(callback) {// 口诀：中左右
    //     let stack = [];
    //     let node = this.root;
    //     while (node || stack.length) {// 将所有孩子结点压栈
    //       if (node) {
    //         callback(node);// 中先于左
    //         stack.push(node);
    //         node = node.left;// 压入left
    //       } else {
    //         node = stack.pop();
    //         node = node.right;// 压入right
    //       }
    //     }
    // }
    // //   inOrder(callback) {// 口诀：左中右
    // //     let stack = [];
    // //     let node = this.root;
    // //     let list = [];
    // //     while (node || stack.length) {// 将所有孩子结点压栈
    // //       if (node) {
    // //         stack.push(node);
    // //         node = node.left;// 压入left
    // //       } else {
    // //         node = stack.pop();
    // //         list.push(node);
    // //         callback(node);// 中先于右
    // //         node = node.right;// 压入right
    // //       }
    // //     }
    // //   }
    // //   postOrder(callback) {// 口诀：左右中
    // //     let stack = [];
    // //     let out = [];
    // //     let node = this.root;
    // //     while (node || stack.length) {// 将所有孩子结点压栈
    // //       if (node) {// 类似于preOrder
    // //         stack.push(node);
    // //         out.push(node);// 源于postOrder2的思路
    // //         node = node.right;// 先放右孩子结点 
    // //       } else {
    // //         node = stack.pop();
    // //         node = node.left;// 先放左孩子结点 
    // //       }
    // //     }
    // //     while(out.length){
    // //       callback(out.pop());
    // //     }
    // //  }
//   //   kthNode(root, k){
//   //   //   1
//   //   //   function inOrder(root, array){
//   //   //     if (root == null){
//   //   //       return;
//   //   //     }
//   //   //     inOrder(root.left, array);
//   //   //     array.push(root);
//   //   //     inOrder(root.right, array);
//   //   //   }
//   //   //   if (!root || k < 0)
//   //   //     return nullptr; 
    
//   //   //   let array = [];
//   //   //   inOrder(root, array);
//   //   //   if (k > array.length)
//   //   //     return null;
//   //   //   return array[k - 1];     
//   //   // }
//   //   let index = 0;
//   //   function kth(root, k){
//   //     if(root){
//   //       let node = kth(node.left, k);
//   //       if(node != null){
//   //         return node;
//   //       }
//   //       index ++;
//   //       if(index == k){
//   //         return root;
//   //       }
//   //       node = kth(node.right, k);
//   //       if(node != null){
//   //         return node;
//   //       }
//   //     }
//   //     return null;
//   //   }
//   //   return kth(root, k);
//   // }
//   // 5.2.10　树的广度优先遍历

//   // levelOrder(callback) {
//   //   let queue = [];
//   //   let node = this.root;
//   //   node && queue.push(node);
//   //   while (queue.length) {
//   //     node = queue.shift();// 先进先出
//   //     callback(node);
//   //     if (node.left) {
//   //       queue.push(node.left);
//   //     }
//   //     if (node.right) {
//   //       queue.push(node.right);
//   //     }
//   //   }
//   // }
//   // 5.2.11　树的打印
//   // 1. 纵向打印
//   // toString() {
//   //   let out = [];
//   //   this.preOrder(function (node) {
//   //     let parent = node.parent;
//   //     if (parent) {
//   //       let isRight = parent.right === node;
//   //       // 为了好看，我们加上└── 和├── 这样的装饰
//   //       out.push(parent.prefix + (isRight ? '└── ' : '├── ') + node.data );
//   //       let indent = parent.prefix + (isRight ? '    ' : '│   ');
//   //       node.prefix = indent;
//   //     } else {
//   //       node.prefix = "   ";
//   //       out.push("└──" + node.data);
//   //     }
//   //   });
//   //   return out.join("\n");
//   // }
// }
// // 5.2.1　树的插入操作
// // const t = new Tree();
// // for(let i = 1; i <= 10; i++) {
// //     t.insert(i)
// // }
// // console.log(t, 't');

// function getPostorder(preorder, inorder, postorder) {
//     let root = preorder[0],
//         inLeftTree = [],
//         inRightTree = [],
//         list = inLeftTree;
//         postorder = postorder || [];
//     // 分离出中序遍历的左右树
//     for (let i = 0, n = inorder.length; i < n; i++) {
//       if (inorder[i] !== root) {
//         list.push(inorder[i]);// 根结点不会放在这两个子树中
//       } else {
//         list = inRightTree;
//       }
//     }
//     let boundary = inLeftTree.length,
//         preLeftTree = [],
//         preRightTree = [];
//     // 分离出前序遍历的左右子树
//     for (let i = 1, n = preorder.length; i < n; i++) {  
//       let el = preorder[i];
//       if(preLeftTree.length < boundary){
//         preLeftTree.push(el);
//       }else{
//         preRightTree.push(el);
//       }
//     }
//     // 后序遍历，左树递归
//     if (preLeftTree.length) {
//         getPostorder(preLeftTree, inLeftTree,  postorder);
//     }
//     // 后序遍历，右树递归
//     if (preRightTree.length) {
//       getPostorder(preRightTree, inRightTree, postorder);
//     }
//     // 后序遍历，处理根
//     if (root) {
//       postorder.push(root);
//     }
//     return postorder;
//   }
//   // let preorder = "GDAFEMHZ".split("");
//   // let inorder = "ADEFGHMZ".split("");
//   // console.log(getPostorder(preorder, inorder));// A E F D H Z M G**
// //   5.2.8　深度优先遍历的非递归实现
//   // function Node(val){
//   //   this.data = val;
//   //   this.left = this.right = null;
//   // }
//   // let tree = new Tree();
//   // let root = tree.root = new Node(40);
//   // root.left = new Node(20);
//   // root.right = new Node(50);
//   // root.left.left = new Node(10);
//   // root.left.right = new Node(30);
//   // root.right.left = new Node(55);
//   // root.right.right  = new Node(51);
//   // // console.log(root, 'root');
//   // let array = [];
//   // tree.preOrder(function(node){
//   //   array.push(node.data);
//   // }); 
//   // console.log(array);// [40, 20, 10, 30, 51, 50, 55]


// 5.2.11　树的打印
// let tree = new SBT(); 
// [10, 50, 40, 30, 20, 60, 55, 54, 53, 52, 51, 56].forEach(function (el, i) {
//   tree.insert(el);
// });
// console.log(tree + "");// 相当于tree.toString()

// 2. 横向打印
// let levelOrder = function(root) {
//   let queue = [];
//   root && queue.push(root, 0);
//   let ret = [];
//   while(queue.length){
//     let el =  queue.shift();
//     let level = queue.shift();
//     if(ret[level]){
//       ret[level].push(el.val);
//     }else{
//       ret[level] = [el.val];
//     }

//     el.left && queue.push(el.left, level+1 );
//     el.right && queue.push(el.right, level+1);
//   }
//   return ret;
// }

function levelOrder( root) {
  let res = [];
  levelHelper(res, root, 0);
  return res;
}
    
function levelHelper( res,  root,  height) {
  if (root == null) return;
  if (!res[height]) {
    res.push([]);
  }
  res[height].push(root);
  levelHelper(res, root.left, height+1);
  levelHelper(res, root.right, height+1);
}
class BST {
  constructor() {
    this.root = null;
    this._size = 0;
  }
  precursor(node){
    let ret;
    if(node.left){// 如果有左子树
      ret = node.left;
      while(ret.right){// 在左子树中查找最大的右结点
        ret = ret.right;
      }
      return ret;
    } else {
      let p = node.parent;
      while(p && p.left === node){
        node = p;// 找到一个父结点，是其父结点的父结点的左孩子结点
        p = p.parent;
      }
      return p;
    }
  }
  successor(node){
    if(node.right){// 如果有右子树
      let ret = node.right;
      while(ret.left){// 在右子树中查找最大的左结点
        ret = ret.left
      }
      return ret;
    }else{
      let p = node.parent;
      while(p && p.right === node){
        node = p;// 找到一个父结点，是其父结点的父结点的右孩子结点
        p = p.parent;
      }
      return p;
    }  
  }
insert(data) {
  var n = new Node(data);
  if (this.root == null) {
    this.root = n;
    this._size++;
    return true;
  }
  var current = this.root;
  var parent;
  while (true) {
    parent = current;
    if(data === current.data) return false;
    n.parent = parent;
    this._size++;
    if (data < current.data) {
      current = current.left;
      if (current == null) {
        parent.left = n;
        break;
      }
    } else {
      current = current.right;
      if (current == null) {
        parent.right = n;
        break;
      }
    }
  } 
}
  find(data) {
    let node = this.root;
    while (node) {
      if (node.data === data) {
        return node;
      } else if (node.data < data) {
        node = node.right;
      } else if (node.data > data) {
        node = node.left;
      }
    }
    return node;
  }
  transplant(){}
  remove(data) {
    let p = this.find(data);
      if (p) {
        this.removeNode(p);// 方便递归
        this._size--;
    }
 }
  // remove里面的辅助方法removeNode
  removeNode(node) {
    // 如果删除的结点左右“孩子”都有
    if (node.left != null && node.right != null) {
      let succ = null;
      for (succ = node.right; succ.left != null; succ = succ.left); // 找到后继结点
      node.data = succ.data; // 覆盖值
      this.removeNode(succ); // 递归删除，只可能递归一次
    } else {
      // 叶子结点或只有一个孩子结点的情况
      let child = node.left || node.right || null;
      this.transplant(node, child);
    }
  }
  preOrder(callback) {// 口诀：中左右
    let stack = [];
    let node = this.root;
    while (node || stack.length) {// 将所有孩子结点压栈
      if (node) {
        callback(node);// 中先于左
        stack.push(node);
        node = node.left;// 压入left
      } else {
        node = stack.pop();
        node = node.right;// 压入right
      }
    }
}
  inOrder(callback) {// 口诀：左中右
    let stack = [];
    let node = this.root;
    let list = [];
    while (node || stack.length) {// 将所有孩子结点压栈
      if (node) {
        stack.push(node);
        node = node.left;// 压入left
      } else {
        node = stack.pop();
        list.push(node);
        callback(node);// 中先于右
        node = node.right;// 压入right
      }
    }
  }
  postOrder(callback) {// 口诀：左右中
    let stack = [];
    let out = [];
    let node = this.root;
    while (node || stack.length) {// 将所有孩子结点压栈
      if (node) {// 类似于preOrder
        stack.push(node);
        out.push(node);// 源于postOrder2的思路
        node = node.right;// 先放右孩子结点 
      } else {
        node = stack.pop();
        node = node.left;// 先放左孩子结点 
      }
    }
    while(out.length){
      callback(out.pop());
    }
 }
    size(){
        return this._size; // this.getNodeSize(this.root)
    }
    maxNode(node) {
      var cur = node || this.root;
      while (cur.right) {
        cur = cur.right;
      }
      return cur;
    }
    minNode(node) {
      var cur = node || this.root;
      while (cur.left) {
        cur = cur.left;
      }
      return cur;
    }
    getMax() {
      var node = this.maxNode();
      return node ? node.data : null;
    }
    getMin() {
      var node = this.minNode();
      return node ? node.data : null;
    }
      getNodeSize(node){
        if (node == null){
          return 0;
        }
        let leftChildSize = this.getNodeSize(node.left);
        let rightChildSize = this.getNodeSize(node.right);
        return leftChildSize + rightChildSize + 1;
    }
    height(){
        return this.getNodeHeight(this.root);
    }
      // 获取指定结点的度
    getNodeHeight(node){
        if (node === null){// 递归出口
          return 0;
        }
        let leftChildHeight = this.getNodeHeight(node.left);
        let rightChildHeight = this.getNodeHeight(node.right);
        let max = Math.max(leftChildHeight, rightChildHeight);
        return max + 1; // 加上自己本身
    }
  printNodeByLevel(callback) {
    let queue = [];
    let node = this.root;
    if (node) {
      queue.push(node);
      queue.push(0);
    }
    while (queue.length) {
      node = queue.shift();// 先进先出
      if (node) {
        callback(node);
        if (node.left) {
          queue.push(node.left);
        }
        if (node.right) {
          queue.push(node.right);
        }
      } else if(queue.length){
        callback(node);// 输出0
        queue.push(0) ;
      }
    }
    callback(0);
  }
  // toString() {
  //   let allLevels = [];
  //   let curLevel = [];
  //   this.printNodeByLevel(function (node) {
  //     if (node === 0) {// 当前层已经结束
  //       allLevels.push(curLevel);
  //       curLevel = [];
  //     } else {
  //       curLevel.push(node.data);// 收集每一层的值
  //     }
  //   });
  //   return allLevels.map(function(el){
  //     return el.join(",");
  //   }).join("\n");
  // }
  toString(displayData) {
    // 辅助方法，让数据居中对齐
    const brickLen = 6, SW = " ", LINE = "_";
    displayData = displayData || function (node) {
      let s = "(" + node.data + ")", right = true, isLeaf = !node.left && !node.right;
      for (let i = s.length; i < brickLen; i++) {
        if (right) {
          s = s + (isLeaf ? SW : LINE);
        } else {
          s = (isLeaf ? SW : LINE) + s;
        }
        right = !right;
      }
      return s;
    };
    // 创建4个字符的空白或下划线
    function createPadding(s, n) {
      let ret = "";
      n = n || brickLen;
      for (let i = 0; i < n; i++) {
        ret += s;
      }
      return ret;
    }
    // ====================================
    // 添加索引值
    let index = 0;
    tree.inOrder(function (el) {
      el.index = index++;
    });
    // 收集每一层的结点
    let allLevels = [];
    let curLevel = [];
    tree.printNodeByLevel(function (node) {
      if (node === 0) {// 当前层的结束标记
        allLevels.push(curLevel);
        curLevel = [];
      } else { // 收集当前层
        curLevel.push(node);
      }
    });
    // brickes中有数据的层，branches只是用来放斜线的层，都是二维数组
    let brickes = [];
    let branches = [];
    for (let i = 0, n = allLevels.length; i < n; i++) {
      if (!brickes[i]) {
        brickes[i] = [];
        branches[i] = [];
      }
      let cbrick = brickes[i];
      let cbranch = branches[i];
      let level = allLevels[i];
      while (level.length) {
        let el = level.shift();
        let j = el.index;
        // 确保cbrick[j]与cbranch[j]等长
        cbrick[j] = displayData(el);
        cbranch[j] = createPadding(SW, cbrick[j].length);
        if (el.parent) {
          let pbrick = brickes[i - 1];
          let pbranch = branches[i - 1];
          let pindex = el.parent.index;
          if (el == el.parent.left) {// 左子树
            for (let k = j + 1; k < pindex; k++) {
              pbrick[k] = createPadding(LINE);
            }
            for (let k = j + 1; k < pindex; k++) {
              pbranch[k] = createPadding(SW);
            }
            pbranch[j] = createPadding(SW, brickLen - 1) + "/";
          } else {// 右子树
            for (let k = pindex + 1; k < j; k++) {
              pbrick[k] = createPadding(LINE);
            }
            for (let k = pindex + 1; k < j; k++) {
              pbranch[k] = createPadding(SW);
            }
            pbranch[j] = "\\" + createPadding(SW, brickLen - 1);
          }
        }
        j--;
        inner:
        while (j > -1) { // 添加空白
          if (cbrick[j] == null) {// 将非空结点变成空字符串
            cbrick[j] = createPadding(SW);
            cbranch[j] = createPadding(SW);
          } else {
            break inner;
          }
          j--;
        }
      }
    }
    return brickes.map(function (el, i) {
      return el.join("") + "\n" + branches[i].join("");
    }).join("\n");
  }
  show(node, parentNode) {
    node = node || this.root;
    if (!parentNode) {
      parentNode = document.createElement("div");
      document.body.appendChild(parentNode);
      this.uuid =  this.uuid  || "uuid" + (new Date - 0);
      parentNode.id = this.uuid;
      let top = parentNode.appendChild(document.createElement("center"));
      top.style.cssText = "background:"+bg();
      top.innerHTML = node.data;
    }
    let a = parentNode.appendChild(document.createElement("div"));
    a.style.cssText = "overflow:hidden";
    if (node.left) {
      let b = a.appendChild(document.createElement("div"));
      b.style.cssText = "float:left; width:49%;text-align:center;background:"+bg();
      b.innerHTML = node.left.data;
      this.show(node.left, b);
    }
    if (node.right) {
      let c = a.appendChild(document.createElement("div"));
      c.style.cssText = "float:right; width:49%;text-align:center;background:"+bg();
      c.innerHTML = node.right.data;
      this.show(node.right, c);
    }
  }
}
function bg() {
  return '#' + (Math.random() * 0xffffff << 0).toString(16);
}

// let tree = new BST(); // 10, 50, 40, 30, 20, 60, 55, 54, 53, 52, 51, 56
// [10, 50, 47, 30, 200, 60, 55, 504, 53, 52, 51, 56].forEach(function (el, i) {
//   tree.insert(el);
// });
// console.log(tree + "");

let tree = new BST();
String("7,15,5,3,9,8,10,13,20,18,25").split(",").forEach(function(a) {
  tree.insert(~~a);
});
let str = "";
tree.inOrder(function(a) {
  str += " " + a.data;
});
console.log(str);
str = "";
tree.preOrder(function(a) {
  str += " " + a.data;
});
console.log(str);
str = "";
tree.postOrder(function(a) {
  str += " " + a.data;
});
console.log(str);
str = "";
console.log("============");
tree.remove(25);
tree.inOrder(function(a) {
  str += " " + a.data;
});
console.log(str);

tree.show();

